#leetcode题目79：单词搜索
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(1)
#方法：回溯

from typing import List
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False
        m,n=len(board),len(board[0])
        def dfs(i,j,k):
            if not 0<=i<m or not 0<=j<n or board[i][j]!=word[k]:
                return False
            elif k==len(word)-1:
                return True
            else:
                board[i][j]=''
                res=dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i,j+1,k+1)
                board[i][j]=word[k] #回溯
                return res
        
        for i in range(m):
            for j in range(n):
                if dfs(i,j,0):
                    return True
        return False

#测试数据
board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word="ABCCED"
#预期输出：True
solution=Solution()
print(solution.exist(board,word))

board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word="SEE"
#预期输出：True
solution=Solution()
print(solution.exist(board,word))

board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word="ABCB"
#预期输出：False
solution=Solution()
print(solution.exist(board,word))
